<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>День 2. Динамика.Base</h2>
<ol>
  <li>Простая квадратная динамика (10 минут)</li>
  <ol>
    <li>Условие: грид, есть стенки, в клетках числа, идем из (1,1) в (n,n), ходить можно только вправо и вверх.</li>
    <li>Количество путей за O(n<sup>2</sup>).</li>
    <li>Динамика вперед и назад на примере "количество путей".</li>
    <li>Ленивая динамика на примере "количество путей".</li>
    <li>Минимальная сумма на пути за O(n<sup>2</sup>).</li>
    <li>Восстанавливаем путь.</li>
    <li>Делаем память линейной (но путь восстановить не можем).</li>
    <li>Более сложная задача: можно ходить вверх, влево, вправо.</li>
  </ol></li>
  <li>Строковые квадратные динамики</li>
  <ol>
    <li>Наибольшая общая подпоследовательсноть за O(n<sup>2</sup>)</li>
    <li>O(n) памяти.</li>
    <li>Восстановление ответа. При восстановлении переходы можно не хранить.</li>
    <li>Наибольшая общая подпоследовательсноть с n<sup>2</sup> / 8 байт памяти и восстановлением ответа.</li>
    <li>Подходит ли строка под шаблон из букв ? и * за O(n<sup>2</sup>)</li>
  </ol></li>
  <li>Рюкзак за O(nw)</li>
  <ol>
    <li>Условие: есть n предметов, нужно взять какие-то, чтобы получилось ровно w.</li>
    <li>Решение за O(nw).</li>
    <li>Делаем память линейной.</li>
    <li>Восстанавливаем ответ (не перезаписываем ячейки, которые уже достигли).</li>
    <li>Случай, когда одну вещь можно брать бесконечное количество раз.</li>
    <li>Задача с весами: максимизировать сумму весов. С линейной памятью можно найти только сумму, ответ восстановить нельзя.</li>
    <li>Решение за O(n*2<sup>n/2</sup>) (meet-in-the-middle)</li>
  </ol></li>
  <li>Разбиения на слагаемые</li>
  <ol>
    <li>За O(n<sup>3</sup>) [sum, максимальное слагаемое], переход = перебираем, какое следующее</li>
    <li>За O(n<sup>2</sup>) [sum, максимальное слагаемое], два перехода</li>
    <li>Делаем память линейной.</li>
    <li>Две разные задачи: можно брать одинаковые слагаемые, все слагаемые должны быть различны</li>
    <li>Еще две задачи: максимальное слагаемое ровно k, максимальное слагаемое не более k за O(nk).</li>
    <li>Ровно на k слагаемых за O(nk) времени и O(n) памяти = перевернуть матрицу</li>
    <li>Ровно на k различных слагаемых за O(n sqrt n) и O(n) памяти: n -= k(k+1)/2</li>
  </ol></li>
  <li>Динамика по подмножествам</li>
  <ol>
    <li>Битовые операции: объединение, пересечение, разность, i-й элемент, является ли A подмножеством B</li>
    <li>Битовые операции: Количество бит в числе за O(1), старший бит за O(1)</li>
    <li>Гамильтонов путь за O(n<sup>2</sup>*2<sup>n</sup>)</li>
    <li>Гамильтонов цикл за O(n<sup>2</sup>*2<sup>n</sup>)</li>
    <li>Количество подклик в графе за O(2<sup>n</sup>*n<sup>2</sup>) и за O(2<sup>n</sup>*n) (битовые операции)</li>
    <li>Количество подклик в графе за O(2<sup>n</sup>) (два решения = рекурсивный перебор или динамика)</li>
    <li>Перебор всех подмножеств циклом for (b = A; b > 0; b--, b &= A)</li>
    <li>Перебор всех надмножеств циклом for (b = A; b < 2<sup>n</sup>; b++, b |= A)</li>
    <li>Количество способов разбить графа на подклики за O(3<sup>n</sup>)</li>
  </ol></li>
  <li>Динамика по подотрезкам  (если останется время)</li>
  <ol>
    <li>Удалить из скобочной последовательности минимальное число скобок, чтобы она стала правильной. O(n<sup>3</sup>).</li>
    <li>Задачка про произведение матриц. O(n<sup>3</sup>).</li>
    <li>Задачка про минимизацию штрафа (удаляем числа по очереди). O(n<sup>3</sup>).</li>
  </ol></li>
</ol>
